package demo2;

import java.util.*;

public class Solution {

    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        char[] ch = s.toCharArray();
        int left = 0, right = 0, t = 0;

        while(right < ch.length){
            char in = ch[right];
            map.put(in, map.getOrDefault(in, 0) + 1);

            while(map.get(in) > 1){
                char out = ch[left++];
                map.put(out, map.get(out) - 1);
            }
            if(right - left + 1 > t){
                t = right - left + 1;
            }
            right++;
        }
        return t;
    }

    public int maximumLengthSubstring(String s) {
        int[] ch = new int[26];

        int left = 0, right = 0, len = 0;
        while(right < s.length()){
            char in = s.charAt(right);
            ch[in - 'a']++;

            while(ch[in - 'a'] > 2){
                char out = s.charAt(left++);
                ch[out - 'a']--;
            }

            if(right - left + 1 > len){
                len = right - left + 1;
            }
            right++;
        }
        return len;
    }

    public static int longestSubarray(int[] nums) {
        int left = 0, right = 0, t = 0, ret = 0;
        while(right < nums.length){
            if(nums[right] == 0) { t++;}

            while(t > 2){
                if(nums[left++] == 0){
                    t--;
                }
            }

            if(right - left + 1> ret){
                ret = right - left + 1;
            }
            right++;
        }
        return ret - t;
    }

    public int longestSubarray2(int[] nums) {
        int n = nums.length;

        int[] l = new int[n];
        int[] r = new int[n];

        l[0] = nums[0];
        for(int i = 1; i < n; i++){
            l[i] = nums[i] != 0 ? l[i - 1] + 1 : 0;
        }

        r[n - 1] = nums[n - 1];
        for(int i = n - 2; i >= 0; i--){
            r[i] = nums[i] != 0 ? r[i + 1] + 1 : 0;
        }

        int ret = 0;
        for(int i = 0; i < n; i++){
            int prev = i == 0 ? 0 : l[i - 1];
            int suf = i == n - 1 ? 0 : r[i + 1];
            ret = Math.max(ret, prev + suf);
        }
        return ret;
    }

    public static int longestSubarray3(int[] nums) {
        int left = 0, right = 0, ret = 0, t = 0;

        while(right < nums.length){
            t += 1 - nums[right];
            while(t > 1){
                t -= 1 - nums[left++];
            }
            ret = Math.max(ret, right - left);
            right++;
        }
        return ret;
    }

    public int equalSubstring(String s, String t, int maxCost) {
        char[] s1 = s.toCharArray();
        char[] s2 = t.toCharArray();
        int n = s1.length;
        int[] num = new int[n];
        for(int i = 0; i < n; i++){
            num[i] = Math.abs(s1[i] - s2[i]);
        }

        int sum = 0, ret = 0;
        for(int left = 0, right = 0; right < n; right++){
            sum += num[right];

            while(sum > maxCost){
                sum -= num[left++];
            }
            if(sum <= maxCost){
                ret = Math.max(ret, right - left + 1);
            }
        }
        return ret;
    }

    public int totalFruit(int[] fruits) {
        int n = fruits.length, kind = 0, ret = 0;
        int[] num = new int[n];

        for(int left = 0, right = 0; right < n; right++){
            int in = fruits[right];
            if(num[in] == 0) { kind++;}
            num[in]++;

            while(kind > 2){
                int out = fruits[left++];
                num[out]--;
                if(num[out] == 0) { kind--;}
            }

            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    public int maximumUniqueSubarray(int[] nums) {
        int ret = 0, sum = 0;
        int[] hash = new int[10010];

        for(int left = 0, right = 0; right < nums.length; right++){
            sum += nums[right];
            hash[nums[right]]++;

            while(hash[nums[right]] == 2){
                sum -= nums[left];
                hash[nums[left]]--;
                left++;
            }

            ret = Math.max(ret, sum);
        }
        return ret;
    }

    public int maxSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> hash = new HashMap<>();

        int ret = 0, t = 0;
        for(int left = 0, right = 0; right < n; right++){
            hash.put(nums[right], hash.getOrDefault(nums[right], 0) + 1);

            while(hash.get(nums[right]) > k){
                hash.put(nums[left], hash.get(nums[left]) - 1);
                left++;
            }

            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    public int maxConsecutiveAnswers(String answerKey, int k) {
        int t = 0, f = 0, ret = 0;
        int n = answerKey.length();
        char[] s = answerKey.toCharArray();

        for(int left = 0, right = 0; right < n; right++){
            if(s[right] == 'T'){
                t++;
            }else{
                f++;
            }

            while(t > k && f > k){
                if(s[left++] == 'T'){
                    t--;
                }else{
                    f--;
                }
            }
            ret = Math.max(ret, f + t);
        }
        return ret;
    }

    public int longestOnes(int[] nums, int k) {
        int zero = 0, ret = 0;
        for(int left = 0, right = 0; right < nums.length; right++){
            if(nums[right] == 0) { zero++;}

            while(zero > k){
                if(nums[left++] == 0) { zero--;}
            }

            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    public int minOperations(int[] nums, int x) {
        int sum = 0, target = 0, ret = -1;
        for(int t : nums) { sum += t;}
        target = sum - x;
        sum = 0;
        if(target < 0) { return -1;}

        for(int left = 0, right = 0; right < nums.length; right++){
            sum += nums[right];

            while(sum > target){
                sum -= nums[left++];
            }
            if(sum == target){
                ret = Math.max(ret, right - left + 1);
            }
        }
        return ret == -1 ? -1 : nums.length- ret;
    }

    public int longestSemiRepetitiveSubstring(String s) {
        char[] ch = s.toCharArray();
        int same = 0, ret = 1;
        for(int left = 0, right = 1; right < ch.length; right++){
            if(ch[right] == ch[right - 1]) { same++;}

            if(same > 1){
                left++;
                while(ch[left] != ch[left - 1]) { left++;}
                same = 1;
            }

            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }


    public static void main(String[] args) {
        System.out.println(longestSubarray(new int[]{1,1,0,1}));
    }
}
